1. Field of the Invention
The present invention is directed to computer systems; and more particularly, it is directed to the rendering of curves using computer systems.
2. Description of the Related Art
As the power and complexity of personal computer systems increase, graphics operations are increasingly being performed using dedicated graphics rendering devices referred to as graphics processing units (GPUs). As used herein, the terms “graphics processing unit” and “graphics processor” are used interchangeably. GPUs are often used in removable graphics cards that are coupled to a motherboard via a standardized bus (e.g., AGP or PCI Express). GPUs may also be used in game consoles and in integrated graphics solutions (e.g., for use in some portable computers and lower-cost desktop computers). Although GPUs vary in their capabilities, they may typically be used to perform such tasks as rendering of two-dimensional (2D) graphical data, rendering of three-dimensional (3D) graphical data, accelerated rendering of graphical user interface (GUI) display elements, and digital video playback. A GPU may implement one or more application programmer interfaces (APIs) that permit programmers to invoke the functionality of the GPU.
A GPU may include various built-in and configurable structures for rendering digital images to an imaging device. Digital images may include raster graphics, vector graphics, or a combination thereof. Raster graphics data (also referred to herein as bitmaps) may be stored and manipulated as a grid of individual picture elements called pixels. A bitmap may be characterized by its width and height in pixels and also by the number of bits per pixel. Commonly, a color bitmap defined in the RGB (red, green blue) color space may comprise between one and eight bits per pixel for each of the red, green, and blue channels. An alpha channel may be used to store additional data such as per-pixel transparency values.
Vector graphics data may be stored and manipulated as one or more geometric objects built with geometric primitives. The geometric primitives (e.g., points, lines, polygons, Bézier curves, and text characters) may be based upon mathematical equations to represent parts of vector graphics data in digital images. The geometric objects may typically be located in two-dimensional or three-dimensional space. To render vector graphics on raster-based imaging devices (e.g., most display devices and printers), the geometric objects are typically converted to raster graphics data in a process called rasterization.
Graphical data may often be expressed in a structured format that complies with a particular specification or model for representing such data. Instead of requiring application programs to describe every page as a full-resolution pixel array, a high-level imaging model may enable applications to describe the appearance of pages containing text, graphical shapes, and sampled images in terms of abstract graphical elements rather than directly in terms of device pixels. Such specifications and models may often be implemented across multiple computing platforms to facilitate the exchange of graphical data. The Adobe® PostScript® language, Adobe® Portable Document Format, and Adobe® Imaging Model, for example, include various structures and commands to describe complex two-dimensional graphical data including geometric models and bitmapped images.
One geometric object typically used in imaging models is the Bézier curve. A quadratic Bézier curve is a parametric curve defined by three control points (P0, P1, P2) in a plane or in three-dimensional space. Starting at P0 and ending at P2, the curve is influenced by the position of an additional control point P1. A rational quadratic Bézier curve is a quadratic Bézier curve defined by a rational fraction of quadratic polynomials. A conic is a quadratic Bézier curve that is an ellipse, parabola, or hyperbola. A normal quadratic Bézier curve is a special case of the conics. A cubic Bézier curve is a parametric curve defined by four control points. A cubic Bézier curve may typically be represented by two or more quadratic Bézier curves, although in some cases a cubic Bézier curve may be represented using only one quadratic Bézier curve (such as the degenerate case where the cubic is itself a line or a quadratic). A typical approach to rendering curves on a GPU is to “flatten” the curve by breaking it into a series of line segments that approximate the shape of the original curve.
One approach for rendering quadratic Bézier curves is described in “Resolution Independent Curve Rendering Using Programmable Graphics Hardware” (Charles Loop and Jim Blinn, ACM SIGGRAPH 2005, pages 1000-1009). In the Loop and Blinn approach, a quadratic Bézier curve is mapped to a canonical Bézier curve represented by the implicit equation y−x2=0 in the canonical coordinate space. The mapping is a linear transformation. The coordinates from the canonical curve are attached as texture parameters to the vertices of the quadratic Bézier curve in design coordinate space and are sent to the GPU. The GPU hardware interpolates the canonical curve parameters and passes them to a pixel shader. The pixel shader uses the canonical curve parameters in the implicit equation to determine if a point is above or below the curve and to clip or paint the point accordingly. However, in extending the Loop and Blinn approach to rational quadratic curves, additional computation is required to find another canonical representation because the mapping is no longer a direct assignment of known canonical values.